package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

public class _538_accumulate_tree {
    
    /**
     * 啊？就这？
     * 不用分成两个方法。。
     * */
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
    int sum;
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.right);
        root.val += sum;
        sum = root.val;
        dfs(root.left);
    }
    
    /**
     * 复习一下 morris 吧
     * 确实又忘了
     *
     * 还行，手把手又背了一遍，估摸着，还得背三四遍，就记住了
     *
     * */
    public TreeNode convertBST2(TreeNode root) {
        TreeNode node = root;
        int sum = 0;
        while (node != null) {
            if (node.right == null) {
                node.val += sum;
                sum = node.val;
                node = node.left;
            }
            else {
                TreeNode suc = succ(node);
                if (suc.left == null) {
                    suc.left = node;
                    node = node.right;
                } else {
                    node.val += sum;
                    sum = node.val;
                    suc.left = null;
                    node = node.left;
                }
            }
        }
        return root;
    }
    TreeNode succ(TreeNode root) {
        TreeNode node = root.right;
        while (node.left != null && node.left != root) {
            node = node.left;
        }
        return node;
    }
}
